Data signals, in particular those transmitted over a typically hostile RF interface (communication channel), are susceptible to error (channel noise) caused by the interface. Various methods of error correction coding have been developed in order to minimize the adverse effects that a hostile interface has on the integrity of communicated data. This is also referred to as lowering the Bit Error Rate (BER), which is generally defined as the ratio of incorrectly received information bits to the total number of received information bits. Error correction coding generally involves representing digital data in ways designed to be robust with respect to bit errors. Error correction coding enables a communication system to recover original data from a signal that has been corrupted.
Two types of error correction code are convolutional code and parallel concatenated convolutional code (so called turbo code). A convolutional code transforms input sequence of bits into an output sequence of bits through the use of finite-state-machine, where additional bits are added to the data stream to provide error-correction capability. In order to increase error-correction capability, the amount of additional bits added and the amount of memory present in the finite-state-machine need to be increased, which increases decoding complexity.
In the turbo coding system, a block of data may be encoded with a particular coding method resulting in systematic bits and two sets of parity bits. For generating a second set of parity bits, the original block of input data is rearranged with an interleaver and then encoded with the same method as that applied to the original input data used to generate a first set of parity bits. Encoded data (systematic bits and parity bits) are combined in some manner to form a serial bit stream and transmitted through the communication channel to a turbo decoding system. Turbo decoding systems operate on noisy versions of the systematic bits and the two sets of parity bits in two decoding stages to produce an estimate of the original message bits. The turbo decoding system uses an iterative decoding algorithm and consists of interleaver and deinterleaver stages individually matched to constituent decoding stages. The decoding stages of the turbo decoding system may use the BCJR algorithm, which was originally invented by Bahl, Cocke, Jelinek, and Raviv to solve a maximum a posteriori probability (MAP) detection problem. The BCJR algorithm is a MAP decoding algorithm in that it minimizes the bit errors by estimating the a posteriori probabilities of the individual bits in a code word. To reconstruct the original data sequence, the soft outputs of the BCJR algorithm are hard-limited. The decoding stages exchange with each other the obtained soft output information and iteration of decoding is ceased when a satisfactory estimate of the transmitted information sequence has been achieved.
As the turbo code has impressive performance, which is very close to Shannon capacity limits, the 3G mobile radio systems such as W-CDMA and cdma2000 have adopted turbo codes for channel coding.
3G wireless systems support a variable bit rate, which may result in full reconstruction of the turbo interleaver at every 10 ms or 20 ms frame. Accordingly, generating the whole interleaved address pattern at once consumes much time and requires a large-sized RAM to store the pattern.
Accordingly, a high speed turbo interleaver which can support a variable bit rate and that does not affect the performance of the turbo coder is required.
As is well-known, W-CDMA and cdma2000 transmission schemes are different in coding rate and interleaving. For example, the coding rate of W-CDMA can be ½, ⅓, ¼ or ⅕ but the coding rate of cdma2000 is ⅓, and the frame size of the W-CDMA is one of twelve numbers 378, 370, 762, . . . , and 20730, but that of the cdma2000 is an arbitrary integer between 40 and 5114, and the row size of the block interleaver in W-CDMA is 32 (8-14 of them are unused) but that of the cdma2000 can be 5, 10, or 20.
Accordingly, flexible and programmable decoders are required for 3G communication because global roaming is recommended between different 3G standards and the frame size may change on a frame base.